#include "disjointset.h"

DisjointSet::DisjointSet(int size)
{
	this->size = size;
	links = new int[size];
	ranks = new int[size];

	for(int i = 0; i < size; i++)
	{
		links[i] = -1;
		ranks[i] = 0;
	}
}

DisjointSet::~DisjointSet()
{
	delete[] links;
	delete[] ranks;
}

int DisjointSet::find(int i)
{
	/* devuelve el conjunto al que pertenece el elemento i */

	list< int > values;

	while(links[i] != -1)
	{
		values.push_back(i);
		i = links[i];
	}

	/* path-compression */
	for(list< int >::const_iterator it = values.begin(); it != values.end(); it++)
	{
		links[*it] = i;
	}

	return i;
}

bool DisjointSet::join(int i, int j)
{
	/* une conjuntos según el rank */

	assert((links[i] == -1 and links[j] == -1) && "i y/o j no son conjuntos");

	if(i == j)
	{
		return false;
	}

	if(ranks[i] > ranks[j])
	{
		links[j] = i;
		//ranks[i] = ranks[j] + 1;
	}
	else
	{
		links[i] = j;
		if(ranks[i] == ranks[j])
			ranks[j] = ranks[i] + 1;
	}

	return true;
}

ostream& operator<<(ostream &os, const DisjointSet &ds)
{
	os << "elemts: ";
	for(int i = 0; i < ds.size; i++)
		os << setw(4) << i;
	os << endl;

	os << "links:  ";
	for(int i = 0; i < ds.size; i++)
		os << setw(4) << ds.links[i];
	os << endl;

	os << "ranks:  ";
	for(int i = 0; i < ds.size; i++)
		os << setw(4) << ds.ranks[i];
	os << endl;

	return os;
}